﻿using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;
using System.Text;
using MPI;

namespace Dwarf.Managed
{
    /// <summary>
    /// This solver is an instance of the 1/0 Knapsack problem that showcases 
    /// dynamic programming in its solution.  
    /// </summary>

    /// <remarks> 
    /// Dynamic programming is a technique used when a problem can be solved in 
    /// terms of optimal solutions of instance sub-problems.
    /// 
    /// The 0/1 Knapsack Problem is as follows: Given a set of items, each with
    /// a given value and cost, and a maximum cost C, determine the set of items that can
    /// be included in the knapsack set without exceeding cost C.  The problem 
    /// is additionally constrained such that there may be either 0 or 1 instance
    /// of a given item included in the knapsack. 
    /// 
    /// This solver uses a bottom-up approach to dynamic programming for solving 
    /// the 0/1 Knapsack problem, finding a solution in terms of optimal sub-problems.
    /// </remarks>
    class Solver
    {

        /// <summary>
        /// The settings for this dwarf.
        /// </summary>
        private Settings SettingsContainer;

        /// <summary>
        /// The maximal cost parameter as given on the first line of the input file.
        /// </summary>
        private int MaximumCost = 0;

        /// <summary>
        /// The list of items with their associated costs and values.
        /// </summary>
        private List<Item> Items = null;

        /// <summary>
        /// The optimal solutions for costs 0..MaximumCost after Solve() has returned.
        /// </summary>
        private Solution[] Answers = null;

        /// <summary>
        /// My unique process rank in the computation.
        /// </summary>
        private int Rank;

        /// <summary>
        /// The number of processes in the computation.
        /// </summary>
        private int Size;

        /// <summary>Constructor</summary>
        /// <param name="args">The command line arguments passed upon startup.</param>
        public Solver(string[] args)
        {
            //Determine the rank of this process.
            Rank = Communicator.world.Rank;

            //Determine the number of processes in the computation.
            Size = Communicator.world.Size;

            SettingsContainer = new Settings();
            SettingsContainer.GetSettings(args); //parse command line arguments

            Items = SettingsContainer.GetItems();
            MaximumCost = SettingsContainer.GetMaxCost();
        }

        /// <summary>MPI based method to solve the 0/1 Knapsack problem.</summary>
        /// <remarks>
        /// The serial algorithm used here is described at http://en.wikipedia.org/wiki/Knapsack_problem. 
        /// It is in effect the following: A[i] = max(v_j + A[i-c_j] | c_j is less than or equal to i). 
        /// Note: It is assumed that for all items, the cost of the item is greater than zero.
        /// </remarks>
        public void Solve()
        {
            //Broadcast the maximum cost constraint.
            Communicator.world.Broadcast<int>(ref MaximumCost, 0);

            //Allocate the Answers array.
            Answers = new Solution[MaximumCost + 1];

            Solution.Answers = Answers;
            Solution.Items = Items;

            //Create an answer for zero weight that has zero value.
            Answers[0] = new Solution(0, 0, -1, -1);

            List<Item> CandidateItems = null;

            //The zero value solution is initially the best solution.
            Solution CurrentMax = Answers[0];

            //Broadcast the items read in from the input file.
            Communicator.world.Broadcast<List<Item>>(ref Items, 0);

            //Limit the items used by this process to a subset.
            if (Rank < Size - 1)
            {
                Items = Items.GetRange(Rank * (Items.Count / Size), Items.Count / Size);
            }
            else
            {
                //Be sure to include all of the items.
                Items = Items.GetRange(Rank * (Items.Count / Size), Items.Count - ((Items.Count / Size) * (Size - 1)));
            }

            Solution SubProblem = null;

            for (int i = 1; i <= MaximumCost; ++i)
            {
                //Get each item that can be considered at the current cost i.
                CandidateItems = Items.FindAll((TestItem) => TestItem.Cost <= i);

                //CurrentMax is always the best solution for the previous round when starting a new round.
                CurrentMax = Answers[i - 1];

                //Determine the node-local maximum value solution.
                //For each item that can be considered
                foreach (Item it in CandidateItems)
                {
                    //Get the optimal sub-problem for the remaining cost alottment
                    SubProblem = Answers[i - it.Cost];

                    //If the cost of it and the sub-problem is less than i...
                    if (SubProblem.Cost + it.Cost <= i) 
                    {
                        //If the value of it and the sub-problem is greater than the current maximum...
                        if (CurrentMax.Value <= (it.Value + SubProblem.Value)) 
                        {
                            //Make sure the sub-problem does not already contain it (this is the 0/1 constraint)
                            if (!SubProblem.ContainsItem(it.Number))
                            {
                                //The best solution so far has been found for cost i
                                CurrentMax = new Solution(SubProblem.Cost + it.Cost, SubProblem.Value + it.Value, it.Number, i - it.Cost);
                            }
                        }
                    }
                }

                //Once all solutions have been tried for cost i, the best overall solution (for cost i) is in CurrentMax for this node.
                //Store this solution for cost i in Answers on all of the processes.
                Answers[i] = Communicator.world.Allreduce<Solution>(CurrentMax, (a, b) => (a.Value >= b.Value) ? a : b);

            }
        }

        public void Finish(double Time)
        {
            if (Rank == 0)
            {
                SettingsContainer.Finish(Time, Answers);
            }
        }
    }
    /// <summary>
    /// A class representing the items being considered for inclusion in the knapsack.
    /// </summary>
    [Serializable]
    public class Item
    {
        /// <summary>
        /// The cost of this item.
        /// </summary>
        private int myCost;
        /// <summary>
        /// The value of this item.
        /// </summary>
        private int myValue;
        /// <summary>
        /// An identifier for this item that is unique for the item's input set.
        /// </summary>
        private int myNumber;

        public Item(int cost, int value, int number)
        {
            myCost = cost;
            myValue = value;
            myNumber = number;
        }

        /// <summary>
        /// The cost of this item.
        /// </summary>
        public int Cost { get { return myCost; } }
        /// <summary>
        /// The value of this item.
        /// </summary>
        public int Value { get { return myValue; } }
        /// <summary>
        /// An identifier for this item that is unique in the item's input set.
        /// </summary>
        public int Number { get { return myNumber; } }

        /// <summary>
        /// Format the Item's data in a string.
        /// </summary>
        /// <returns>A string representing the data elements of this Item.</returns>
        public override string ToString()
        {
            return myNumber + ": " + myCost + ", " + myValue;
        }
    }

    /// <summary>
    /// A class representing a solution for the 0/1 knapsack problem.
    /// </summary>
    [Serializable]
    public class Solution
    {
        public static Solution[] Answers;
        public static List<Item> Items;

        /// <summary>
        /// The value of this solution.
        /// </summary>
        private int myValue;
        /// <summary>
        /// The cost of this solution.
        /// </summary>
        private int myCost;
        /// <summary>
        /// The item added to another solution to form this solution.
        /// </summary>
        private int myItemIndex;
        // private Item myItem;
        /// <summary>
        /// The solution added to another item to form this solution.
        /// </summary>
        private int mySubSolutionIndex;
        // private Solution mySubSolution;

        public Solution(int cost, int value, int itemIndex, int subSolutionIndex)
        {
            myCost = cost;
            myValue = value;
            myItemIndex = itemIndex;
            mySubSolutionIndex = subSolutionIndex;
        }

        /// <summary>
        /// Tests whether this solution contains an item labeled with itemNumber.
        /// </summary>
        /// <param name="itemNumber">The identifier of an item to search for in this solution.</param>
        /// <returns>True if an Item with the specified itemNumber is part of this solution.  False otherwise.</returns>
        public bool ContainsItem(int itemNumber)
        {
            bool returnValue = false;
            //If I have an item...
            if (myItemIndex >= 0)
            {
                //check to see whether itemNumber is my Item...
                if (myItemIndex == itemNumber)
                {
                    //if so -- return true
                    returnValue = true;
                }
                else
                {
                    //if not -- check mySubSolution to see if itemNumber is used there.
                    if (mySubSolutionIndex >= 0)
                    {
                        returnValue = Answers[mySubSolutionIndex].ContainsItem(itemNumber);
                    }
                }
            }
            return returnValue;
        }

        /// <summary>
        /// The value of this solution.
        /// </summary>
        public int Value { get { return myValue; } }
        /// <summary>
        /// The cost of this solution.
        /// </summary>
        public int Cost { get { return myCost; } }

        public Item[] GetItemsArray() {
            List<Item> items = new List<Item>();
            Solution solution = this;
            while (solution != null) {
                if (solution.myItemIndex >= 0)
                    items.Add(Items[solution.myItemIndex]);
                solution = solution.mySubSolutionIndex >= 0 ? Answers[solution.mySubSolutionIndex] : null;
            }
            items.Sort((x, y) => x.Number < y.Number ? -1 : x.Number > y.Number ? 1 : 0);
            return items.ToArray();
        }

        /// <summary>
        /// Format the data within this solution as a string.
        /// </summary>
        /// <returns>A string representing the solution.</returns>
        public override string ToString()
        {
            StringBuilder sb = new StringBuilder();
            Item[] items = GetItemsArray();
            foreach (Item item in items) {
                sb.Append(item.ToString());
                sb.Append(System.Environment.NewLine);
            }
            return sb.ToString();
        }
    }
}